Un arbre (Tree) est une structure de données hiérarchique non linéaire qui simule les architectures organisationnelles du monde réel (comme un système de fichiers ou un arbre généalogique). Contrairement aux listes, piles et files d'attente dont l'organisation est linéaire, l'essence d'un arbre réside dans sanature hiérarchique (Hierarchical)etnature récursive (Recursive).
1. Analyse de la forme d'un arbre
- nœud (Node): unité fondamentale contenant une clé (Key) et une charge utile.
- nœud racine (Root): le seul nœud sans arête entrante, constituant le point de départ de l'arbre.
- arête (Edge): le chemin unique reliant deux nœuds, représentant la relation parent-enfant.
- nœud feuille (Leaf): nœud terminal sans enfants, constituant la frontière naturelle d'arrêt de la récursion.
2. Deux perspectives pour définir un arbre de manière récursive
Nous pouvons comprendre un arbre à partir de deux points de vue :
perspective graphique
un graphe acyclique et connexe composé de nœuds et d'arêtes, où chaque nœud (sauf la racine) possède exactement un parent.
un graphe acyclique et connexe composé de nœuds et d'arêtes, où chaque nœud (sauf la racine) possède exactement un parent.
perspective récursive
un arbre est soit vide, soit constitué d'une racine et de zéro ou plusieurs sous-arbres (Subtree).
un arbre est soit vide, soit constitué d'une racine et de zéro ou plusieurs sous-arbres (Subtree).
Exemple d'arbre DOM HTML
Dans HTML,
<html> est la racine,<body> et <head> sont des nœuds frères. Chaque balise et son contenu imbriqué forment ensemble un sous-arbre. Cette structure permet de déplacer globalement <ul> ainsi que tous ses <li> sans altérer leur hiérarchie interne.